A group signature scheme allows members to sign messages anonymously on behalf of the group. A person examining the signature can then obtain the assurance that the signer is a member of the group, without being able to identify which member it is. It is often implemented so that an authorized authority remains able to lift the anonymity of any signature when needed.
To allow revocation of a group member, the scheme must also have mechanisms to prevent a member from signing after such a revocation. Two main techniques exist:                one which requires updating the keys of all non-revoked members and updating the public key for the system,        the other which requires the verifier to test whether or not a given signature was generated from a revoked key. A revocation list then contains elements characterizing the set of these revoked keys.        
In certain contexts, it is undesirable to require the users to connect regularly to the database of public elements in order to update their keys, as this operation can be costly in terms of computation.
The second technique, called group signature with verifier-local revocation (VLR), is considered here. It typically makes use of algorithms having the following functionalities:                generation of keys, namely a public key shared by all protagonists of the scheme, respective private keys of the various members of the signer group, a secret key of the group manager, and a secret key of the revocation manager;        signature, allowing each member having a private key to sign anonymously for the group;        revocation, allowing a revocation manager to add a member to the list of revoked members;        signature verification, allowing anyone having the public key to ensure that a given signature does indeed come from a non-revoked member of the signer group (without being able to determine which member);        opening a signature . . . .        
A VLR technique for group signature that does not have the ability to lift anonymity was introduced by Boneh and Shacham in “Group Signatures with Verifier-Local Revocation”, Proceedings of the 11th ACM Conference on Computer and Communications Security, Washington D.C., USA, ACM, 2004, pp. 168-177. Aside from the inability to lift anonymity, which is a desirable property in many cases, this system has the limitation of not maintaining the anonymity of prior signatures (backward unlinkability). This property of maintaining anonymity ensures that revoking a member does not compromise the anonymity of all previous signatures of this member. This property is often desirable, particularly when the revoked member is honest.
In “Verifier-Local Revocation Group Signature Schemes with Backward Unlinkability from Bilinear Maps”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2007, E90-A(1), pp. 65-74, Nakanishi and Funabiki proposed a variation in which time is divided into a number of periods with the number being fixed at system creation. Each period has a corresponding element in the public key of the system (necessary to produce a signature), and to each revoked member there corresponds as many elements in the revocation list as there are periods. This technique, which also does not include the lifting of anonymity, has the disadvantage that a revoked key can continue to be used to produce group signatures as long as the current period has not ended. It is therefore necessary to compromise between the length of a period and the size of the public elements and revocation list.
There is no current technique that provides a strong secrecy preservation property, in which an adversary accessing the private key of a member of the signer group is unable to determine which signatures were made by this member.
In “Shorter Verifier-Local Revocation Group Signatures From Bilinear Maps” (Lecture Notes in Computer Science, Cryptology and Network Security, Volume 4301, 2006, pp. 126-143), Zhou and Lin presented a VLR group signature scheme allowing the lifting of anonymity. An anonymity lifting manager, which holds a secret key, is then able to partially reveal the private key of the member who signed a given message. The mechanism for opening or lifting anonymity in this article requires an exhaustive search among the members of the group, making this an unattractive system.